Android LruCache源码分析，图片缓存算法的实现原理

程序员小乐 2020-10-08

专注于编程、互联网动态。最终将总结的技术、心得、经验（数据结构与算法、源码分析等）分享给大家，这里不只限于技术！还有职场心得、生活感悟、以及面经。点击上方 "程序员小乐" ，关注公众号，第一时间送达！

每日英文

Different people do the same thing for you,which would make you feel extremely different.Because what you care for is not the thing,but rather for the person who do it.

不同的人，为你做同一件事，你会感到天壤之别。因为我们在意的，往往不是人做的事，而只是做事的人。

小乐有话说

没有走不通的路，没有过不去的坎。相信自己，我们都有可能创造奇迹！

来自：枫叶栈

链接：jianshu.com/u/dfd117c5b6de

封面来自网络

00 LruCache概要

LRU (Least Recently Used) 即最近最少使用算法。在Android开发中，LruCache是基于LRU算法实现的。当缓存空间使用完的情况下，最久没被使用的对象会被清除出缓存。

LruCache常用的场景是做图片内存缓存，电商类APP经常会用到图片，当我们对图片资源做了内存缓存，不仅可以增强用户体验，而且可以减少图片网络请求，减少用户流量耗费。

LruCache是一个内存层面的缓存，如果想要进行本地磁盘缓存，推荐使用DiskLruCache，虽然没包含在官方API中，但是官方推荐我们使用。

01 使用方法

LruCache的使用方法如下：

public class BitmapLruCache extends LruCache<String, Bitmap> { 
    //设置缓存大小，建议当前应用可用最大内存的八分之一 即(int) (Runtime.getRuntime().maxMemory() / 1024 / 8) 
    public BitmapLruCache(int size) { 
        super(size); 
    } 

    //计算当前节点的内存大小 这个方法需要重写 不然返回1 
    @Override 
    protected int sizeOf(String key, Bitmap value) { 
        return value.getByteCount() / 1024; 
    } 

    //当节点移除时该方法会回调，可根据需求来决定是否重写该方法 
    @Override 
    protected void entryRemoved(boolean evicted, String key, Bitmap oldValue, Bitmap 
            newValue) { 
        super.entryRemoved(evicted, key, oldValue, newValue); 
    } 
}

往缓存中放一张图片：

mLruCache.put(name, bitmap);

获取一张图片：

mLruCache.get(name);

删除一张图片：

mLruCache.remove(name);

02 源码分析

首先先看一下LruCache构造方法

public LruCache(int maxSize) { 
    if (maxSize <= 0) { 
        throw new IllegalArgumentException("maxSize <= 0"); 
    } 
    this.maxSize = maxSize; 
    //我们发现实现用的是LinkedHashMap   注意最后的true 表示LinkedHashMap 中accessOrder设置为true 
    this.map = new LinkedHashMap<K, V>(0, 0.75f, true); 
}

接着，我们继续来看下put方法

/** 
 * Caches {@code value} for {@code key}. The value is moved to the head of 
 * the queue. 
 * 
 * @return the previous value mapped by {@code key}. 
 */ 
public final V put(K key, V value) { 
    if (key == null || value == null) {//不允许key 和 value 为 null 
        throw new NullPointerException("key == null || value == null"); 
    } 

    V previous; 
    synchronized (this) {//多线程安全 
        putCount++; 
        //size 表示当期使用的缓存大小  safeSizeOf 会掉用sizeOf方法 用于计算当前节点的大小 
        size += safeSizeOf(key, value); 
        // 将新节点放入LinkedHashMap 如果有返回值，表示map集合中存在旧值 
        previous = map.put(key, value); 
        if (previous != null) {//存在旧值 在移除旧值后 更新缓存大小 
            size -= safeSizeOf(key, previous); 
        } 
    } 
    //有旧值移除 回调entryRemoved 
    if (previous != null) { 
        entryRemoved(false, key, previous, value); 
    } 
    trimToSize(maxSize);//整理每个节点 主要判断当前size是否超过maxSize  
    return previous; 
} 

public void trimToSize(int maxSize) { 
    while (true) { 
        K key; 
        V value; 
        synchronized (this) { 
            if (size < 0 || (map.isEmpty() && size != 0)) { 
                throw new IllegalStateException(getClass().getName() 
                            + ".sizeOf() is reporting inconsistent results!"); 
            } 
            //size <= maxSize 停止遍历列表，不然继续遍历列表修剪节点。  
            if (size <= maxSize || map.isEmpty()) { 
                break; 
            } 

            Map.Entry<K, V> toEvict = map.entrySet().iterator().next(); 
            key = toEvict.getKey(); 
            value = toEvict.getValue(); 
            map.remove(key); 
            size -= safeSizeOf(key, value); 
            evictionCount++; 
        } 

        entryRemoved(true, key, value, null); 
    } 
}

再来看下safeSizeOf 和 entryRemoved方法

private int safeSizeOf(K key, V value) { 
        int result = sizeOf(key, value);//调用了sizeOf方法 
        if (result < 0) { 
            throw new IllegalStateException("Negative size: " + key + "=" + value); 
        } 
        return result; 
    } 


  protected int sizeOf(K key, V value) {//sizeOf的默认实现 
        return 1; 
    } 

protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {}//entryRemoved的默认实现

get方法

/** 
 * Returns the value for {@code key} if it exists in the cache or can be 
 * created by {@code #create}. If a value was returned, it is moved to the 
 * head of the queue. This returns null if a value is not cached and cannot 
 * be created. 
 */ 
public final V get(K key) { 
    if (key == null) {//key不能为 null 
        throw new NullPointerException("key == null"); 
    } 

    V mapValue; 
    synchronized (this) {//线程同步 
        mapValue = map.get(key);//调用LinkedHashMap 的get方法 
        if (mapValue != null) { 
            hitCount++; 
            return mapValue;//找到返回 
        } 
        missCount++; 
    } 

    /* 
     * Attempt to create a value. This may take a long time, and the map 
     * may be different when create() returns. If a conflicting value was 
     * added to the map while create() was working, we leave that value in 
     * the map and release the created value. 
     */ 

    V createdValue = create(key);//缓存没有情况下走创建流程 
    if (createdValue == null) { 
        return null; 
    } 

    synchronized (this) { 
        createCount++; 
        mapValue = map.put(key, createdValue); 

        if (mapValue != null) { 
            // There was a conflict so undo that last put 
            map.put(key, mapValue); 
        } else { 
            size += safeSizeOf(key, createdValue); 
        } 
    } 

    if (mapValue != null) { 
        entryRemoved(false, key, createdValue, mapValue); 
        return mapValue; 
    } else { 
        trimToSize(maxSize); 
        return createdValue; 
    } 
} 


protected V create(K key) {//创建方法默认空实现 可根据需求决定是否重写该方法 
    return null; 
}

最后，我们来看下remove方法

/** 
 * Removes the entry for {@code key} if it exists. 
 * 
 * @return the previous value mapped by {@code key}. 
 */ 
public final V remove(K key) { 
   if (key == null) { 
       throw new NullPointerException("key == null"); 
   } 

   V previous; 
   synchronized (this) {//线程同步 
       previous = map.remove(key);//获得移除的节点 
       if (previous != null) {//当节点不为空 更新缓存大小 
           size -= safeSizeOf(key, previous); 
       } 
   } 

   if (previous != null) { 
      //当节点移除时回调entryRemoved方法 
       entryRemoved(false, key, previous, null); 
   } 

   return previous; 
}

通过上述几个方法代码，我们知道LruCache如何控制及更新缓存的大小的，主要是在线程同步块里对size字段进行更新,然后根据size字段和maxSize字段的大小关系来修剪节点。但如何做到最近最少使用呢？没错，LinkedHashMap 帮我们做到最近最少使用的排序。

让我们看下LinkedHashMap 如何实现的，在此过程我们不分析HashMap的实现，只关心LinkedHashMap 的一些实现，HashMap的实现有机会给大家分享。

//继承了HashMap 说明LinkedHashMap 的查找效率依然是O(1) 
public class LinkedHashMap<K,V> 
    extends HashMap<K,V> 
    implements Map<K,V> 
{ 
   //重新定义了节点 用于实现链表 
    private transient LinkedHashMapEntry<K,V> header; 

 private static class LinkedHashMapEntry<K,V> extends HashMapEntry<K,V> { 
        LinkedHashMapEntry<K,V> before, after; 
        //此处省略几个字 
} 
    //此处省略几个字 
}

LinkedHashMap类并没有重写put方法，当我们调用put方法时，调用的依然是HashMap的put方法。我们看下HashMap的put方法：

public V put(K key, V value) { 
        if (table == EMPTY_TABLE) { 
            inflateTable(threshold); 
        } 
        if (key == null) 
            //HashMap的特点 可以放key为null的值 
            return putForNullKey(value); 
        int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key); 
        int i = indexFor(hash, table.length); 
        for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) { 
            Object k; 
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 
                V oldValue = e.value; 
                e.value = value; 
                e.recordAccess(this); 
                return oldValue;//存在旧值 就把旧值移除掉 并返回旧值  由此可知 当我们更换缓存中已存在的值时，并不会影响它在链表中位置 
            } 
        } 

        modCount++; 
        addEntry(hash, key, value, i);//LinkedHashMap 重写了该方法 
        return null; 
    } 

 //LinkedHashMap中实现  
 void addEntry(int hash, K key, V value, int bucketIndex) { 
        // Previous Android releases called removeEldestEntry() before actually 
        // inserting a value but after increasing the size. 
        // The RI is documented to call it afterwards. 
        // **** THIS CHANGE WILL BE REVERTED IN A FUTURE ANDROID RELEASE **** 

        // Remove eldest entry if instructed 
        LinkedHashMapEntry<K,V> eldest = header.after; 
        if (eldest != header) { 
            boolean removeEldest; 
            size++; 
            try { 
                removeEldest = removeEldestEntry(eldest);//hook  默认为false 让用户重写removeEldestEntry 来决定是否移除eldest节点 
            } finally { 
                size--; 
            } 
            if (removeEldest) { 
                removeEntryForKey(eldest.key); 
            } 
        } 

        super.addEntry(hash, key, value, bucketIndex);//往下瞅 有惊喜 
    } 

  protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { 
        return false; 
    } 


   //HashMap中addEntry： 
   void addEntry(int hash, K key, V value, int bucketIndex) { 
        if ((size >= threshold) && (null != table[bucketIndex])) { 
            resize(2 * table.length); 
            hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0; 
            bucketIndex = indexFor(hash, table.length); 
        } 
         //LinkedHashMap重写了该方法 
        createEntry(hash, key, value, bucketIndex); 
    } 

    //LinkedHashMap中 
    void createEntry(int hash, K key, V value, int bucketIndex) { 
        HashMapEntry<K,V> old = table[bucketIndex]; 
        LinkedHashMapEntry<K,V> e = new LinkedHashMapEntry<>(hash, key, value, old); 
        table[bucketIndex] = e; 
       //把该节点插入到链表头部 最近使用访问到的在最前边原则 
        e.addBefore(header);  
        size++; 
    }

LinkedHashMap中重写了get方法，实现如下;

public V get(Object key) { 
    //使用HashMap的getEntry方法，验证了我们所说的查询效率为O(1) 
    LinkedHashMapEntry<K,V> e = (LinkedHashMapEntry<K,V>)getEntry(key); 
    if (e == null) 
        return null; 
    e.recordAccess(this);//在找到节点后调用节点recordAccess方法 往下看 
    return e.value; 
} 

//LinkedHashMapEntry 
void recordAccess(HashMap<K,V> m) { 
    LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m; 
    if (lm.accessOrder) {//accessOrder该值默认为false 但是  在LruCache中设置为true 
        lm.modCount++; 
        remove();//该方法将本身节点移除链表 
        addBefore(lm.header);//将自己添加到节点头部 保证最近使用的节点位于链表前边 
        } 
    }

LinkedHashMap的并没有重写HashMap的remove方法，依然是调用HashMap的remove方法，代码如下：

public V remove(Object key) { 
    Entry<K,V> e = removeEntryForKey(key); 
    return (e == null ? null : e.getValue()); 
} 

final Entry<K,V> removeEntryForKey(Object key) { 
    if (size == 0) { 
        return null; 
    } 
    int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key); 
    int i = indexFor(hash, table.length); 
    HashMapEntry<K,V> prev = table[i]; 
    HashMapEntry<K,V> e = prev; 

    while (e != null) { 
        HashMapEntry<K,V> next = e.next; 
        Object k; 
        if (e.hash == hash && 
            ((k = e.key) == key || (key != null && key.equals(k)))) { 
            modCount++; 
            size--; 
            if (prev == e) 
                table[i] = next; 
            else 
                prev.next = next; 
            //注意这一行 开头我们说过  LinkedHashMap用的节点是自己定义的LinkedHashMapEntry ，继承自HashMapEntry 
            e.recordRemoval(this); 
            return e; 
        } 
        prev = e; 
        e = next; 
    } 

    return e; 
} 

//LinkedHashMapEntry 中recordRemoval 
void recordRemoval(HashMap<K,V> m) { 
    remove(); 
} 
private void remove() {//更改指针来移除自身 
    before.after = after; 
    after.before = before; 
}

03 demo验证

首先创建LRUCache，我们设置其大小为4，因为默认每个Item大小为1，当我们执行放入操作时，最后放入的数据会在链表最后边，打印结果如下：

private void test() { 
    LruCache<String,String> lruCache = new LruCache<>(4); 
    lruCache.put("a","这是第1个放进去的值"); 
    lruCache.put("b","这是第2个放进去的值"); 
    lruCache.put("c","这是第3个放进去的值"); 
    lruCache.put("d","这是第4个放进去的值"); 
    print(lruCache); 
} 

private void print(LruCache<String,String> lruCache){ 
    Map map =lruCache.snapshot(); 
    Iterator<String> iterator = map.keySet().iterator(); 
    String key; 
    while (iterator.hasNext()){ 
        key = iterator.next(); 
        Log.i("LruCacheItem","key ="+key+"   value ="+map.get(key)); 
    } 
}

测试截图如下：

当我们访问链表中一个元素时候，该元素会移到队列末尾，测试如下:

private void test() { 
    LruCache<String,String> lruCache = new LruCache<>(4); 
    lruCache.put("a","这是第1个放进去的值"); 
    lruCache.put("b","这是第2个放进去的值"); 
    lruCache.put("c","这是第3个放进去的值"); 
    lruCache.put("d","这是第4个放进去的值"); 
    lruCache.get("c"); 
    print(lruCache); 
}

测试截图如下：

我们发现第一个元素被移除。我们会发现key为c的item移到了队列末尾。当我们放入元素超过总的大小时，队列首部元素会被移除：

private void test() { 
    LruCache<String,String> lruCache = new LruCache<>(4); 
    lruCache.put("a","这是第1个放进去的值"); 
    lruCache.put("b","这是第2个放进去的值"); 
    lruCache.put("c","这是第3个放进去的值"); 
    lruCache.put("d","这是第4个放进去的值"); 
    lruCache.get("c"); 
    lruCache.put("e","这是第5个放进去的值"); 
    print(lruCache); 
}

测试截图如下：

我们发现超出总大小后，队列首部元素被移除。移除相对简单，不会改变队列里元素的相对顺序，只是该元素出队列而已，测试如下：

private void test() { 
    LruCache<String,String> lruCache = new LruCache<>(4); 
    lruCache.put("a","这是第1个放进去的值"); 
    lruCache.put("b","这是第2个放进去的值"); 
    lruCache.put("c","这是第3个放进去的值"); 
    lruCache.put("d","这是第4个放进去的值"); 
    lruCache.get("c"); 
    lruCache.put("e","这是第5个放进去的值"); 
    lruCache.remove("c"); 
    print(lruCache); 
}

key为c的元素被移除链表，结果如下：

04 总结

读完源码我们可以总结出：

LruCache是继承自HashMap，它的查找效率依然是O(1);
LruCache内部又维护了一个双向链表结构，当我们有访问操作时候，被访问节点会移到链表前边
在Lrucache的put、get和remove方法中，对集合操作时使用了synchronized关键字，来保证线程安全；

OK，关于LruCache源码实现层面的就分析完了，感谢你的耐心阅读。

如果您觉得不错，请别忘了转发、分享、点赞让更多的人去学习，您的举手之劳，就是对小乐最好的支持，非常感谢！

如何您想进技术群交流，关注公众号在后台回复 “加群”，或者 “学习” 即可
著作权归作者所有，欢迎大家投稿

看完本文有收获？请转发分享给更多人
关注「程序员小乐」，提升技能

清华学生国庆怒怼丘成桐！这事儿到底谁对谁错？

妻子每月收入7000给弟弟寄6000，离婚时，弟弟带着女朋友冲到民政局：“姐，你分到的钱，能帮我们凑个首付吗？

听纪委朋友说，有的领导干部在被抽掉鞋带和皮带后，一下就崩溃了，甚至个别胆小者顿时大小便失禁……

听纪委朋友说，有的领导干部在被抽掉鞋带和皮带后，一下就崩溃了，甚至个别胆小者顿时大小便失禁……

上海超市血案：背后缘由让人揪心

Android LruCache源码分析，图片缓存算法的实现原理

推荐阅读
阿里、腾讯、百度、华为、京东最新面试题汇集
如何选择公司？
MVVM架构使用之我见
OOP之六大设计原则

看完本文有收获？请转发分享给更多人
关注「程序员小乐」，提升技能

您可能也对以下帖子感兴趣

清华学生国庆怒怼丘成桐！ 这事儿到底谁对谁错？

妻子每月收入7000给弟弟寄6000，离婚时，弟弟带着女朋友冲到民政局：“姐，你分到的钱，能帮我们凑个首付吗？

听纪委朋友说，有的领导干部在被抽掉鞋带和皮带后，一下就崩溃了，甚至个别胆小者顿时大小便失禁……

听纪委朋友说，有的领导干部在被抽掉鞋带和皮带后，一下就崩溃了，甚至个别胆小者顿时大小便失禁……

上海超市血案：背后缘由让人揪心

生成图片，分享到微信朋友圈

Android LruCache源码分析，图片缓存算法的实现原理

推荐阅读阿里、腾讯、百度、华为、京东最新面试题汇集如何选择公司？MVVM架构使用之我见OOP之六大设计原则

看完本文有收获？请转发分享给更多人关注「程序员小乐」，提升技能

您可能也对以下帖子感兴趣

清华学生国庆怒怼丘成桐！这事儿到底谁对谁错？

推荐阅读
阿里、腾讯、百度、华为、京东最新面试题汇集
如何选择公司？
MVVM架构使用之我见
OOP之六大设计原则

看完本文有收获？请转发分享给更多人
关注「程序员小乐」，提升技能